package J20250227_dfs;
import java.util.*;
/**
 * Created with IntelliJ IDEA.
 * Description: 递归1——4
 * User: 王圆豪
 * Date: 2025-02-27
 * Time: 11:45
 */

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    //汉诺塔——https://leetcode.cn/problems/hanota-lcci/
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        func(A,B,C,A.size());
    }
    public void func(List<Integer> A, List<Integer> B, List<Integer> C, int n){
        if(n == 1){
            C.add(A.remove(A.size()-1));
            return;
        }
        func(A,C,B,n-1);
        C.add(A.remove(A.size()-1));
        func(B,A,C,n-1);
    }

    //合并两个有序链表——https://leetcode.cn/problems/merge-two-sorted-lists/
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode();
        return dfs(list1, list2);
    }

    public ListNode dfs(ListNode list1, ListNode list2){
        ListNode head = new ListNode();
        if(list1 == null && list2 == null) return null;
        if(list1 == null) {
            head = list2;
            return head;
        }
        if(list2 == null){
            head = list1;
            return head;
        }
        if(list1.val < list2.val){
            head.val = list1.val;
            head.next = dfs(list1.next, list2);
        }else{
            head.val = list2.val;
            head.next = dfs(list1, list2.next);
        }
        return head;
    }

    //反转链表——https://leetcode.cn/problems/reverse-linked-list/
    public ListNode reverseList(ListNode head) {
        return dfs(head);
    }

    public ListNode dfs(ListNode head){
        if(head == null) return null;
        if(head.next == null) return head;
        ListNode newhead = dfs(head.next);
        head.next.next = head;
        head.next = null;
        return newhead;
    }

    //两两交换链表中的节点——https://leetcode.cn/problems/swap-nodes-in-pairs/
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode cur = swapPairs(head.next.next);
        ListNode tmp = head.next;
        head.next.next = head;
        head.next = cur;
        return tmp;
    }
}
